package seqlist.leetcode;

public class Num145插入排序 {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummyhed = new ListNode();
        dummyhed.next=head;
        ListNode lastsort=head,cur = head.next;
        while (cur!=null){
            if (lastsort.val<=cur.val){
                lastsort=lastsort.next;
            }else {
                ListNode prev= dummyhed;
                while (prev.next.val<=cur.val){
                    prev=prev.next;
                }
                lastsort.next=cur.next;
                cur.next=prev.next;
                prev.next=cur;
            }
            cur = lastsort.next;
        }
        return dummyhed.next;
    }
}
